Calculating the First and Follow sets

Here are some extracts from the book by Aho that explain the algorithm for calculating these sets.

Here is an example:

The following shows how one can construct a parsing table:

Notes:

• The word "add" in the Steps 2 and 3 above may lead to some confusion: There can be at most a single production rule in each element of the table (at least, if the grammar is LL(1)). If the table element remains empty, the terminal corresponding to the table element should never be the next symbol in the input string when the non-terminal corresponding to the table element is at the top of the parsing stack.

Notes (en français):

• Le mot "add" dans les étapes 2 et 3 ci-hautes porte à la confusion: Il ne peut jamais y avoir plus qu'une seule règle de production dans une case de la table (si la grammaire est LL(1)). Si la case reste vide, alors le terminal correspondant à la case ne devrait jamais être le prochain symbole de l'entrée quand le non-terminal correspondant à la case est au sommet de la pile d'analyse.